\chapter{Problem definition}
\label{chap:problemDefinition}

The following chapter is strongly based on a technical report titled \emph{``Burglar-Game: Planning Used In A Level Design And During A Gameplay''} \cite{burglarICAPSsubmission} written in cooperation with Rudolf Kadlec.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\begin{longtable}{|p{0.9\textwidth}}

In order to formally define the planning problem solved in our game we will use following notation:

$M=\langle Rooms, Doors \rangle$ is a planar graph representing the map of the level where $Rooms$ is the set of all rooms and $Doors$ is a the set of all door objects in the layout. A state of each $door \in Doors$ is given by a function $Ds: Doors \to \{locked, unlocked, opened\}$;

$Objects$ is a set of operable objects; each object $o \in Objects$ can also have its internal state given by function $Os: Objects \to propositions\ about\ objects$. In the implementation of our game for example we have containers that can be \emph{closed} or \emph{opened}; sleeping guards that may or may not have uniforms; or cameras and a vending machines that may be \emph{active} or \emph{disabled}.

The set of active agents we define as $Agents = Guards \cup \{burglar\}$ where $Guards$ is a set of patrolling guards and $burglar$ marks the single burglar agent. 
Each agent in $Agents$ is specified by its starting room, planning goal and knowledge of objects' states, we call this the agent's \emph{belief base}.

$E = Objects \cup Agents$ stands for a set of all entities in the level;
function $EtoR: E \to Rooms$ assigns each entity to one room;
$A$ stands for a set of possible instantiated player's actions on a member of $E$ like deactivating a camera object or locking a door. The full list of such action types is described in section~\ref{sec:contextMenu}.

Now we can define a world state on map $M$ as $S^M = \langle E, Os, EtoR, Ds \rangle \in \mathcal{S^M}$, where $\mathcal{S^M}$ denotes a set of all possible world states on the given layout $M$.

Based on the above definition we will set $S^M_{burglar} \in \mathcal{S^M}$ as the state of the world believed to be true by the burglar, and $S^M_{real} \in \mathcal{S^M}$ as the real state of the world perceivable by the human player.

A game level $L$ we define as a triplet $\langle M, S^M_{real}, S^M_{burglar} \rangle$. Predicate $flawed(P,S^M)$ is true if execution of a plan $P$ in a state of the world $S^M$ leads to a situation when the $burglar$ is \emph{caught}. In the game such situation occurs when the burglar and a patrolling guard or an active camera occupies the same room, formally:
$
flawed(P,S^M) =
\begin{cases}
true  & P~\text{results in}~\exists camera: (Os(camera) = active~\wedge \\
      &       EtoR(camera) = EtoR(burglar))~\vee \\
      &       \exists guard: EtoR(guard) = EtoR(burglar) \\
false & otherwise
\end{cases}
$

Such rooms where the $burglar$ gets caught we will call \emph{trap rooms}.

From now on we omit the upper index in $S^M$ since we take $M$ as fixed.
%   $n \in N$ is a required number of minimal player's changes of the world and $a \in

To capture the effect of the player's actions on the burglars knowledge, we define an auxiliary function 
$
H(\bar{A}, S_{burglar}) = S'_{burglar}
$.
It models a situation where the player executes actions $\bar{A} \subseteq A$ and due to theirs effect burglar updates his belief to the new state $S'_{burglar}$.

Now we can define the problem that has to be solved in design time as finding at least some solutions of function 
$F: \mathcal{S} \times \mathbb{N} \to 2^{\mathcal{S}}$. $F$ gets an initial world state $S_{init}$ and a number of pitfalls $n$ both provided by the designer and outputs the set of world states that can be known to the burglar at the beginning of the game.

We will now discuss the definition of function $F$ that is implemented by our prototype:

\begin{gather}
 S_{burglar} \in F(S_{real},n)  \equiv \nonumber \\
 \exists P:\neg flawed(P, S_{burglar}) \wedge flawed(P, S_{real})~\wedge \label{eq:believable} \\ 
\exists \bar{A}  \subseteq A: H(\bar{A}, S_{burglar}) = S'_{burglar}~\wedge \label{eq:userAct} \\
|trapRoomsPresentInPlan(P)|=n~\wedge \label{eq:trapRooms} \\
\exists P': \neg flawed(P', S'_{burglar}) \wedge \neg flawed(P', S_{real}) \label{eq:ok}
\end{gather}

We require that there is a plan that seems to be solving the task given the burglar's initial knowledge, but it contains pitfalls in reality (Condition~\ref{eq:believable}), further there must be the user's actions that make the burglar change its belief base to the new state $S'_{burglar}$ (Condition~\ref{eq:userAct}), the number of trap rooms in the plan must be $n$ (Condition~\ref{eq:trapRooms}) and there must be the new plan $P'$ that is without trap rooms both in $S'_{burglar}$ and $S_{real}$ (Condition~\ref{eq:ok}).

It must be noted that our definition guarantees only the creation of traps, but not required user's actions. It can lead to creating levels where the initial burglar's plan contains $n$ pitfalls, but it can be solved with just one user's action leading the burglar to the plan $P'$ that is solving correctly the problem in $S'_{burglar}$.

For the details of our implementation see chapter~\ref{chap:creatingGameLevels}.
%\end{longtable}


